#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

/*
1930. 长度为 3 的不同回文子序列
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。
 

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)
示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。
示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)
 

提示：

3 <= s.length <= 105
s 仅由小写英文字母组成
*/

// 法一
class Solution {
    public:
    int countPalindromicSubsequence(string s) {
        int n = s.size();                   // 获取字符串 s 的长度
        int count = 0;                      // 用于记录回文子序列的个数
        for (char c = 'a'; c <= 'z'; c++) { // 遍历小写字母
            int left = 0, right = n - 1;    // 初始化左右指针
            // 找到字符 c 在字符串中最左边的位置
            while (left < n && s[left] != c) {
                left++;
            }
            // 找到字符 c 在字符串中最右边的位置
            while (right >= 0 && s[right] != c) {
                right--;
            }
            // 如果存在字符 c 且左右指针位置合法
            if (left < right) {
                std::unordered_set<char> uniqueChars; // 存储中间字符的集合
                // 遍历中间部分，统计不同的字符
                for (int i = left + 1; i < right; i++) {
                    uniqueChars.insert(s[i]);
                }
                count += uniqueChars
                             .size(); // 累加不同字符的数量，即回文子序列的数量
            }
        }
        return count; // 返回回文子序列的总个数
    }
};

// 法二
class Solution {
    public:
    int countPalindromicSubsequence(string s) {
        int n = s.size();
        int ans = 0;
        // 前缀/后缀字符状态数组
        vector<int>pre(n), suf(n);
        for(int i=0;i<n;++i) {
            // 前缀s[0..i-1] 包含的字符种类
            pre[i] = (i ? pre[i-1] : 0) | (1 << (s[i] - 'a'));
        }
        for(int i=n-1;i>=0;i--) {
            // 后缀s[i+1..n-1] 包含的字符种类
            suf[i] = (i != n-1 ? suf[i+1] : 0) | (1 << (s[i] - 'a'));
        }
        // 每种中间字符的回文子序列状态
        vector<int> res(26);
        for(int i=1;i<n-1;++i) {
            res[s[i] - 'a'] |= (pre[i-1] & suf[i+1]); // 计算每个字母作为中间字符时的状态
        }
           // 更新答案
        for (int i = 0; i < 26; ++i) {
            ans += __builtin_popcount(res[i]);
        }
        return ans;
    }
};